import java.util.*;

import util.MaxHeap;

/**
 * The class implementing Vantage Point search
 *
 */
public class simpleVP extends NN
{
	private Point VP;
	private SortingElement[] distanceList;
	private int k;

	public simpleVP(Point DataBase[], int k)
	{
		super(DataBase);
		Random randomizer = new Random();
		// Choose a random point from database to be the Vantage Point
		VP = DataBase[randomizer.nextInt(pointCount)];
		// Sort all points according to distance to Vantage Point
		distanceList = CreateSortedIndex(VP, DataBase);
		this.k = k;
	}

	public SortingElement[] Query(Point q)
	{
		MaxHeap kNN = new MaxHeap();
		
		Double ref = VP.Distance(q);
		int left = 0, right = pointCount, index = (right + left) / 2;
		Double distance = distanceList[index].value;
	
		// Find the reference point that has the most similar distance to Vantage Point to that of query point using binary search
		while ((left < right) && (right - left > 1))
		{
			if (distance > ref) right = right - (right - left) / 2;
			else if (distance <= ref) left = left + (right - left) / 2;
			index = (right + left) / 2;
			distance = distanceList[index].value; 
		}

		int heapCount = 1;
		int leftPoint = index, rightPoint = index;
		Double leftDelta = Double.MAX_VALUE, rightDelta = Double.MAX_VALUE, delta = 0d;
		distance = DataBase[distanceList[index].index].Distance(q);
		Double upperBound = distance;
		kNN.insert(new SortingElement(distanceList[index].index, distance));

		if (index > 0)
		{
			leftPoint = index - 1;
			leftDelta = distanceList[index].value - distanceList[leftPoint].value;
		}
		if (index < pointCount - 1)
		{
			rightPoint = index + 1;
			rightDelta = distanceList[rightPoint].value - distanceList[index].value;
		}
		
		// search until the nearest distance found so far is within delta (or for k-nearest neighbor, until k point already in the heap)
		while ((leftPoint >= 0 || rightPoint < pointCount) && (delta <= upperBound || heapCount < k))
		{
			Point temp = null;
			// Find whether check the left or the right based on the difference in distance to reference point
			if (leftDelta < rightDelta)
			{
				temp = DataBase[distanceList[leftPoint].index];
				delta = leftDelta;
				if (leftPoint > 0) leftDelta = distanceList[index].value - distanceList[--leftPoint].value;
				else leftDelta = Double.MAX_VALUE;
			}
			else
			{
				temp = DataBase[distanceList[rightPoint].index];
				delta = rightDelta;
				if (rightPoint < pointCount - 1) rightDelta = distanceList[++rightPoint].value - distanceList[index].value;
				else rightDelta = Double.MAX_VALUE;
			}
			if (heapCount < k)
			{
				Double tempDistance = temp.Distance(q);
				kNN.insert(new SortingElement(temp.ID(), tempDistance));
				if (tempDistance > upperBound) upperBound = tempDistance;
				heapCount += 1;
			}
			else
			{
				Double tempDistance = temp.Distance(q);
				if (tempDistance < upperBound)
				{
					kNN.removeMax();
					kNN.insert(new SortingElement(temp.ID(), tempDistance));
					upperBound = ((SortingElement)kNN.max()).value;
				}
			}
		}

		SortingElement[] retVal = new SortingElement[heapCount];
		int i = heapCount - 1;
		while (!kNN.isEmpty()) {retVal[i--] = (SortingElement)kNN.removeMax();}
		return retVal;
	}
}
